Search for: All records

We demonstrate a method for proving precise concentration inequalities in uniformly random trees on $$n$$ vertices, where $$n\geq1$$ is a fixed positive integer. The method uses a bijection between mappings $$f\colon\{1,\ldots,n\}\to\{1,\ldots,n\}$$ and doubly rooted trees on $$n$$ vertices. The main application is a concentration inequality for the number of vertices connected to an independent set in a uniformly random tree, which is then used to prove partial unimodality of its independent set sequence. So, we give probabilistic arguments for inequalities that often use combinatorial arguments. 

Abstract Using the calculus of variations, we prove the following structure theorem for noise-stable partitions: a partition of n -dimensional Euclidean space into m disjoint sets of fixed Gaussian volumes that maximise their noise stability must be $(m-1)$ -dimensional, if $$m-1\leq n$$ . In particular, the maximum noise stability of a partition of m sets in $$\mathbb {R}^{n}$$ of fixed Gaussian volumes is constant for all n satisfying $$n\geq m-1$$ . From this result, we obtain: (i) A proof of the plurality is stablest conjecture for three candidate elections, for all correlation parameters $$\rho $$ satisfying $$0<\rho <\rho _{0}$$ , where $$\rho _{0}>0$$ is a fixed constant (that does not depend on the dimension n ), when each candidate has an equal chance of winning. (ii) A variational proof of Borell’s inequality (corresponding to the case $m=2$ ). The structure theorem answers a question of De–Mossel–Neeman and of Ghazi–Kamath–Raghavendra. Item (i) is the first proof of any case of the plurality is stablest conjecture of Khot-Kindler-Mossel-O’Donnell for fixed $$\rho $$ , with the case $$\rho \to L1^{-}$$ being solved recently. Item (i) is also the first evidence for the optimality of the Frieze–Jerrum semidefinite program for solving MAX-3-CUT, assuming the unique games conjecture. Without the assumption that each candidate has an equal chance of winning in (i), the plurality is stablest conjecture is known to be false. 

We prove the endpoint case of a conjecture of Khot and Moshkovitz related to the unique games conjecture, less a small error. Letn ≥ 2. Suppose a subset Ω ofn‐dimensional Euclidean spacesatisfies −Ω = Ω^cand Ω + v = Ω^c(up to measure zero sets) for every standard basis vector. For anyand for anyq ≥ 1, letand let. For anyx ∈ ∂Ω, letN(x) denote the exterior normal vector atxsuch that ‖N(x)‖₂ = 1. Let. Our main result shows thatBhas the smallest Gaussian surface area among all such subsets Ω, less a small error:In particular,Standard arguments extend these results to a corresponding weak inequality for noise stability. Removing the factor 6 × 10⁻⁹would prove the endpoint case of the Khot‐Moshkovitz conjecture. Lastly, we prove a Euclidean analogue of the Khot and Moshkovitz conjecture. The full conjecture of Khot and Moshkovitz provides strong evidence for the truth of the unique games conjecture, a central conjecture in theoretical computer science that is closely related to the P versus NP problem. So, our results also provide evidence for the truth of the unique games conjecture. Nevertheless, this paper does not prove any case of the unique games conjecture.